/**
 *  @file    test.c
 *  @desc    保留两个升序链表的交集元素，并释放非交集部分内存（链表1被就地修改）
 *  @author  WangBlue (wangjiping596@gmail.com)
 *  @date    2025-07-18 10:14
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 链表结构定义 -------------------------

/**
 * @brief 单链表结点结构（带头结点）
 */
typedef struct node {
    int data;              ///< 数据域
    struct node *next;     ///< 指针域
} node, *link;

// ------------------------- 链表基本操作函数 -------------------------

/**
 * @brief 创建一个新的数据结点（非头结点）
 * @param value 要插入的整数
 * @return 成功返回指向新结点的指针，失败返回 NULL
 */
link createNode(int value) {
    link node = (link)malloc(sizeof(node));
    if (!node) return NULL;
    node->data = value;
    node->next = NULL;
    return node;
}

/**
 * @brief 初始化一个带头结点的空链表
 * @param head 指向头指针的指针
 */
void initNode(link *head) {
    link node = (link)malloc(sizeof(node));
    if (!node) return;
    node->data = 0;      // 头结点 data 无意义
    node->next = NULL;
    *head = node;
}

/**
 * @brief 头插法插入结点
 * @param head 链表头指针（带头结点）
 * @param value 插入的值
 */
void insertHead(link head, int value) {
    if (!head) return;
    link node = createNode(value);
    if (!node) return;
    node->next = head->next;
    head->next = node;
}

/**
 * @brief 尾插法插入结点
 * @param head 链表头指针（带头结点）
 * @param value 插入的值
 */
void insertTail(link head, int value) {
    if (!head) return;
    link node = createNode(value);
    if (!node) return;

    link cur = head;
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = node;
}

/**
 * @brief 打印链表中的所有数据结点
 * @param head 链表头指针（带头结点）
 */
void printList(link head) {
    if (head == NULL) return;
    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 释放整个链表（包括头结点）
 * @param head 指向链表头指针的指针
 */
void destroy(link *head) {
    if (!head || !*head) return;
    link cur = *head;
    while (cur) {
        link temp = cur->next;
        free(cur);
        cur = temp;
    }
    *head = NULL;
    printf("SUCCESS\n");
}

// ------------------------- 核心函数：取交集并释放非交结点 -------------------------

/**
 * @brief 就地修改链表 *la，使其只保留与 lb 的公共元素
 * @details
 *   - la/lb 都是递增链表，带头结点
 *   - lb 不被修改，la 被就地裁剪，非交集部分释放内存
 *   - 最终 la = la ∩ lb，仍保留头结点
 *
 * @param la 指向链表1头指针的指针（被修改）
 * @param lb 链表2头指针（不修改）
 * @return 无返回值，修改通过指针生效
 */
link findIntersection(link *la, link lb) {
    if (la == NULL || (*la)->next == NULL) return NULL;
    if (lb == NULL || lb->next == NULL) return NULL;

    link pa = (*la)->next;   // 遍历链表 la 的当前结点（跳过头结点）
    link pb = lb->next;      // 遍历链表 lb 的当前结点（跳过头结点）
    link preA = *la;         // pa 的前驱，初始指向头结点

    while (pa != NULL && pb != NULL) {
        if (pa->data > pb->data) {
            // lb 结点较小，往后走
            pb = pb->next;
        } else if (pb->data > pa->data) {
            // la 结点较小，需删除该结点（不是交集）
            link temp = pa;
            pa = pa->next;
            free(temp);              // 释放当前结点
            preA->next = pa;         // 前驱跳过当前
        } else {
            // 相等，保留当前结点，三个指针一起后移
            preA = pa;
            pa = pa->next;
            pb = pb->next;
        }
    }

    // la 剩余结点都不在交集，需全部释放
    while (pa != NULL) {
        link temp = pa;
        pa = pa->next;
        free(temp);
    }

    // 最后将前驱指针置 NULL，截断后续
    preA->next = NULL;

    return *la;
}

// ------------------------- 主函数测试 -------------------------

int main() {
    // 初始化链表 head1：1 → 2 → 3
    link head1 = NULL;
    initNode(&head1);
    insertTail(head1, 1);
    insertTail(head1, 2);
    insertTail(head1, 3);

    // 初始化链表 head2：2 → 3 → 4
    link head2 = NULL;
    initNode(&head2);
    insertTail(head2, 2);
    insertTail(head2, 3);
    insertTail(head2, 4);

    // 就地修改 head1，仅保留交集元素（2、3）
    findIntersection(&head1, head2);

    // 打印修改后的 head1：输出 2 和 3
    printList(head1);

    // 内存释放（包含头结点）
    destroy(&head1);
    destroy(&head2);

    return 0;
}
